inf = float('inf')
def floyd_warshall(graph, n):
    # 初始化距离矩阵
    dist = [[inf] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if i == j:
                dist[i][j] = 0
            else:
                dist[i][j] = graph[i][j]
    
    # 动态规划优化路径
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:  # 以k作为中转节点
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    # 检测负权环
    for i in range(n):
        if dist[i][i] < 0:
            print("图中存在负权环")
            return
    
    return dist

# 示例图
graph = [
    [0, 3, 8, inf],
    [inf, 0, 1, 4],
    [inf, inf, 0, 2],
    [inf, inf, inf, 0]
]
n = 4
result = floyd_warshall(graph, n)
for row in result:
    print(row)
